package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.graph.Graph;
import cn.initcap.algorithm.graph.SparseGraph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 哈密尔顿回路
 *
 * @author initcap
 * @date Created in 7/31/19 9:54 AM.
 */
public class HamiltonLoop {

    private Graph<Integer, Double> graph;
    /**
     * 状态压缩
     */
    private int visited;
    /**
     * 记忆化搜索,只有针对大量重复的情况才可以采用，其他情况不建议使用
     */
    private int[][] memo;
    private int[] pre;
    private int end;

    public HamiltonLoop(Graph graph) {
        this.graph = graph;
        end = -1;
        pre = new int[graph.nodeSize()];
        memo = new int[1 << graph.nodeSize()][graph.nodeSize()];
        for (int i = 0; i < memo.length; i++) {
            Arrays.fill(memo[i], -1);
        }
        visited = 0;
        // 从任意一个定点开始都可以
        dfs(0, 0, graph.nodeSize());
    }

    public static void main(String[] args) {
        Graph graph = new SparseGraph("algorithm/testG12.txt", false);
        HamiltonLoop dfs = new HamiltonLoop(graph);
        System.out.println(dfs.result());
    }

    private boolean dfs(int v, int parent, int count) {
        if (memo[visited][v] != -1) {
            return memo[visited][v] == 1;
        }
        visited += (1 << v);
        pre[v] = parent;
        count--;
        if (count == 0 && graph.hasEdge(v, 0)) {
            end = v;
            memo[visited][v] = 1;
            return true;
        }

        for (int w : graph.adj(v)) {
            if ((visited & (1 << w)) == 0) {
                if (dfs(w, v, count)) {
                    memo[visited][v] = 1;
                    return true;
                }
            }
        }
        memo[visited][v] = 0;
        visited -= (1 << v);
        return false;
    }

    public List<Integer> result() {
        List<Integer> res = new ArrayList<>();
        if (end == -1) {
            return res;
        }

        int cur = end;
        while (cur != 0) {
            res.add(cur);
            cur = pre[cur];
        }
        res.add(0);

        Collections.reverse(res);
        return res;
    }

}
